//给你一个下标从 0 开始、大小为 m x n 的二维矩阵 grid ，请你求解大小同样为 m x n 的答案矩阵 answer 。 
//
// 矩阵 answer 中每个单元格 (r, c) 的值可以按下述方式进行计算： 
//
// 
// 令 topLeft[r][c] 为矩阵 grid 中单元格 (r, c) 左上角对角线上 不同值 的数量。 
// 令 bottomRight[r][c] 为矩阵 grid 中单元格 (r, c) 右下角对角线上 不同值 的数量。 
// 
//
// 然后 answer[r][c] = |topLeft[r][c] - bottomRight[r][c]| 。 
//
// 返回矩阵 answer 。 
//
// 矩阵对角线 是从最顶行或最左列的某个单元格开始，向右下方向走到矩阵末尾的对角线。 
//
// 如果单元格 (r1, c1) 和单元格 (r, c) 属于同一条对角线且 r1 < r ，则单元格 (r1, c1) 属于单元格 (r, c) 的左上对角
//线。类似地，可以定义右下对角线。 
//
// 
//
// 示例 1： 
// 
// 
//输入：grid = [[1,2,3],[3,1,5],[3,2,1]]
//输出：[[1,1,0],[1,0,1],[0,1,1]]
//解释：第 1 个图表示最初的矩阵 grid 。 
//第 2 个图表示对单元格 (0,0) 计算，其中蓝色单元格是位于右下对角线的单元格。
//第 3 个图表示对单元格 (1,2) 计算，其中红色单元格是位于左上对角线的单元格。
//第 4 个图表示对单元格 (1,1) 计算，其中蓝色单元格是位于右下对角线的单元格，红色单元格是位于左上对角线的单元格。
//- 单元格 (0,0) 的右下对角线包含 [1,1] ，而左上对角线包含 [] 。对应答案是 |1 - 0| = 1 。
//- 单元格 (1,2) 的右下对角线包含 [] ，而左上对角线包含 [2] 。对应答案是 |0 - 1| = 1 。
//- 单元格 (1,1) 的右下对角线包含 [1] ，而左上对角线包含 [1] 。对应答案是 |1 - 1| = 0 。
//其他单元格的对应答案也可以按照这样的流程进行计算。
// 
//
// 示例 2： 
//
// 
//输入：grid = [[1]]
//输出：[[0]]
//解释：- 单元格 (0,0) 的右下对角线包含 [] ，左上对角线包含 [] 。对应答案是 |0 - 0| = 0 。
// 
//
// 
//
// 提示： 
//
// 
// m == grid.length 
// n == grid[i].length 
// 1 <= m, n, grid[i][j] <= 50 
// 
//
// Related Topics 数组 哈希表 矩阵 👍 30 👎 0


package LeetCode.editor.cn;


import java.util.HashSet;
import java.util.Set;

/**
 * @author ldltd
 * @date 2025-03-25 12:09:09
 * @description 2711.对角线上不同值的数量差
 
 */
 
public class DifferenceOfNumberOfDistinctValuesOnDiagonals {
    public static void main(String[] args) {
    //测试代码
    DifferenceOfNumberOfDistinctValuesOnDiagonals fun = new DifferenceOfNumberOfDistinctValuesOnDiagonals();
    Solution solution= fun.new Solution();
    int [][] ar=new int [][]{{1,2,3},{3,1,5},{3,2,1}};
    solution.differenceOfDistinctValues(ar);
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        //1.暴力不可取
    //2.预计算每条对角线到某个点的不同元素个数保存到数组tl[i][j]
    //对于每个坐标i,j
    //左上角的个数就是tl[i][j]，右下角个数是另i/j为边界的点的个数，
    //两者之差就是结果，所以问题是右下角的个数怎么计算
    //对于一个m x n的矩阵，他其中一个坐标i,j
    //他的右边界坐标im,jm计算为
    //令k=min(m-i-1,n-j-1)
    //im=i+k,jm=j+k
    //这样是不行的，比如左上角是 1 2 右下角也是 1 2 ，则最后右下角只有2个不同的
    //所以还是得分开计算，维护另一个br
    public int[][] differenceOfDistinctValues(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int [][] tl=new int[m][n];
        int [][] br=new int[m][n];
        Set<Integer> set=new HashSet<>();
        for (int i = 0, j = n-1;j>=0; j--) {
            set.clear();
            for (int i1 = i,j1=j; i1<m&&j1<n ; i1++,j1++) {
                tl[i1][j1]=set.size();
                set.add(grid[i1][j1]);
            }
        }
        for (int i = 1, j = 0;i<m; i++) {
            set.clear();
            for (int i1 = i,j1=j; i1<m&&j1<n ; i1++,j1++) {
                tl[i1][j1]=set.size();
                set.add(grid[i1][j1]);
            }
        }
        for (int i = m-1, j = n-1;j>=0; j--) {
            set.clear();
            for (int i1 = i,j1=j; i1>=0&&j1>=0 ; i1--,j1--) {
                br[i1][j1]=set.size();
                set.add(grid[i1][j1]);
            }
        }
        for (int i = m-2, j = n-1;i>=0; i--) {
            set.clear();
            for (int i1 = i,j1=j; i1>=0&&j1>=0 ; i1--,j1--) {
                br[i1][j1]=set.size();
                set.add(grid[i1][j1]);
            }
        }
        int [][] res=new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                res[i][j]=Math.abs(tl[i][j]-br[i][j]);
            }
        }
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
